{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#归并排序\n",
    "def merge_sort(arr):\n",
    "    if len(arr) <= 1:\n",
    "        return arr\n",
    "    mid = len(arr) // 2\n",
    "    left_half = merge_sort(arr[:mid])  # 递归地对左半部分进行归并排序\n",
    "    right_half = merge_sort(arr[mid:])  # 递归地对右半部分进行归并排序\n",
    "    return merge(left_half, right_half)  # 合并左右两部分的结果\n",
    "\n",
    "def merge(left, right):\n",
    "    if not left:  # 如果左半部分为空，直接返回右半部分\n",
    "        return right\n",
    "    if not right:  # 如果右半部分为空，直接返回左半部分\n",
    "        return left\n",
    "    if left[0] <= right[0]:  # 如果左半部分的第一个元素小于等于右半部分的第一个元素\n",
    "        return [left[0]] + merge(left[1:], right)  # 将左半部分的第一个元素与剩余部分合并\n",
    "    else:\n",
    "        return [right[0]] + merge(left, right[1:])  # 将右半部分的第一个元素与剩余部分合并"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#快速排序\n",
    "def quickSort(arr, left=None, right=None):\n",
    "    left = 0 if not isinstance(left,(int, float)) else left\n",
    "    right = len(arr)-1 if not isinstance(right,(int, float)) else right\n",
    "    if left < right:\n",
    "        partitionIndex = partition(arr, left, right)\n",
    "        quickSort(arr, left, partitionIndex-1)\n",
    "        quickSort(arr, partitionIndex+1, right)\n",
    "    return arr\n",
    "\n",
    "def partition(arr, left, right):\n",
    "    pivot = left\n",
    "    index = pivot+1\n",
    "    i = index\n",
    "    while  i <= right:\n",
    "        if arr[i] < arr[pivot]:\n",
    "            swap(arr, i, index)\n",
    "            index+=1\n",
    "        i+=1\n",
    "    swap(arr,pivot,index-1)\n",
    "    return index-1\n",
    "\n",
    "def swap(arr, i, j):\n",
    "    arr[i], arr[j] = arr[j], arr[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#选择排序\n",
    "def selectionSort(arr):\n",
    "    for i in range(len(arr) - 1):\n",
    "        # 记录最小数的索引\n",
    "        minIndex = i\n",
    "        for j in range(i + 1, len(arr)):\n",
    "            if arr[j] < arr[minIndex]:\n",
    "                minIndex = j\n",
    "        # i 不是最小数时，将 i 和最小数进行交换\n",
    "        if i != minIndex:\n",
    "            arr[i], arr[minIndex] = arr[minIndex], arr[i]\n",
    "    return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#插入排序\n",
    "def insertionSort(arr):\n",
    "    for i in range(len(arr)):\n",
    "        preIndex = i-1\n",
    "        current = arr[i]\n",
    "        while preIndex >= 0 and arr[preIndex] > current:\n",
    "            arr[preIndex+1] = arr[preIndex]\n",
    "            preIndex-=1\n",
    "        arr[preIndex+1] = current\n",
    "    return arr"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
